<?php

namespace App\Tools;

use Illuminate\Support\Facades\Cache;
use Illuminate\Support\Facades\DB;
use MathPHP\LinearAlgebra\Vector;
use MathPHP\LinearAlgebra\MatrixFactory;
use App\Product;
use App\UserAction;
use Generator;

class RecommenderSystem
{
    const MAX_FILE_SIZE = 16777216;
    const MAX_PAD = 1048576;
    const EPSILON = 1e-9;
    // 用户、产品 id 和索引之间的映射
    private $map;
    // 用户分块数
    private $k;
    // 存储位置
    private $dataDir;
    // 存储键值对
    private $cacheKeys;

    /**
     * @var int $k 用户分块数, 默认为 1
     * @var string $dataDir 数据存储位置, 默认为 cache
     */
    public function __construct(int $k = 1, string $dataDir = null)
    {
        $this->setChunks($k);
        $this->setDataDir($dataDir);

        $kvs = [
            "map" => "rs.map",
            "user_rating" => "rs.user_rating",
            "sim_mat" => "rs.sim_mat",
            "user_recommender_products" => "rs.user_recommender_products",
        ];
        $this->setCacheKey($kvs);
        $this->generateMap();
    }

    /**
     * 为用户 $uid 产生至多 $numberOfVoter * $numberOfVote 个推荐产品
     * @var int $uid user id
     * @var int $numberOfVoter 选民数
     * @var int $numberOfVote 每个选民的票数
     * @return array
     */
    public function vote($uid, $numberOfVoter, $numberOfVote) : array
    {
        $likes = $this->userLikes($uid, $numberOfVoter);
        $ps = [];
        foreach ($likes as $id) {
            $fps = $this->getUserFavouriteProducts($id, $numberOfVote);
            $ps = array_merge($ps, $fps);
        }
        $ps = array_unique($ps);
        // 推荐产品没有必要存储到文件
        $key = $this->getCacheKey("user_recommender_products");
        Cache::forever("$key.$uid", $ps);
        return $ps;
    }

    /**
     * 计算和用户 $uid 相似度最高的 $n 个用户, 返回由用户 id 组成的数组
     * @var int $uid user's id
     * @var int $n number of user
     * @return array
     */
    public function userLikes($uid, $n = 10) : array
    {
        $likes = [];
        $map = $this->getMap();
        $users = $map["users"];
        $kn = $map["numberPerChunk"];
        // 获取相似度向量
        $vec = $this->getSimVecByUser($uid);
        if (!$vec) {
            return [];
        }
        // 逆排序
        arsort($vec);
        // 前 $n 个索引
        $topNI = array_slice(array_keys($vec), 0, $n);
        // 索引转 id
        $location = $this->userIdToLocation($uid);
        $i = $location[0];
        foreach ($topNI as $j) {
            $likes[] = $users[$i * $kn + $j];
        }

        return $likes;
    }

    /**
     * 得到用户 $id 评分最高的 $n 个产品, 返回产品 id 数组
     * @var int $id user's id
     * @var int $n number of products
     * @return array
     */
    public function getUserFavouriteProducts(int $id, int $n = 10) : array
    {
        $dir = $this->getDataDir();
        $key = $this->getCacheKey("user_rating");
        $map = $this->getMap();
        $pi = $map["products"];
        $iu = $map["indexOfUsers"];
        $m = count($iu);
        $index = $iu[$id];
        if ($dir) {
            $file = $dir . DIRECTORY_SEPARATOR . "$key.csv";
            if (filesize($file) > static::MAX_FILE_SIZE) {
                $csv = fopen($file, "r");
                for ($i = 0; $i < $index; $i++) {
                    fgets($csv);
                }
                $vec = str_getcsv(fgets($csv));
                fclose($csv);
            } else {
                $arr = file($file, FILE_IGNORE_NEW_LINES);
                $vec = str_getcsv($arr[$index]);
            }
        } else {
            $vec = Cache::get("$key.$id");
        }

        arsort($vec);
        $rn = array_slice($vec, 0, $n, true);
        // 删除评分为 0 的项
        $rn = array_filter($rn, function ($item) {
            return abs($item) > 1e-9;
        });
        $fps = [];
        foreach ($rn as $pid => $score) {
            $fps[] = $pi[$pid];
        }

        return $fps;
    }

    /**
     * 得到评分矩阵, 生成当前进度
     * 考虑到数据可能被其他程序使用, 不分块
     * @yield array
     * @return Generator
     */
    public function getRatingVectors() : Generator
    {
        $users = $this->getMap()["users"];
        $key = $this->getCacheKey("user_rating");
        $csv = null;
        $dir = $this->getDataDir();
        if ($dir) {
            $csv = fopen($dir . DIRECTORY_SEPARATOR . $key . ".csv", "w");
        }
        $i = 0;

        foreach ($users as $id) {
            $userRatingVector = $this->getRatingByUser($id);
            if ($csv) {
                fputcsv($csv, $userRatingVector);
            } else {
                Cache::forever("$key.$id", $userRatingVector);
            }
            $i++;
            yield [$i, count($users)];
        }

        if ($csv) {
            fclose($csv);
        }
    }

    /**
     * 得到用户评分向量相似度矩阵
     * 考虑内存限制，将用户分成 $k 组, 求协方差
     * 如果初始化类传入存储位置, 则保存数据到文件
     * 生成当前进度
     * test:
     *     cache, chunk=1: 60s
     * @yield array
     * @return Generator
     */
    public function getSimilarityMatrix() : Generator
    {
        $k = $this->getChunks();
        $dir = $this->getDataDir();
        $users = $this->getMap()["users"];
        $urKey = $this->getCacheKey("user_rating");
        $smKey = $this->getCacheKey("sim_mat");
        $nk = intval(ceil(count($users) / $k));
        if ($dir) {
            $file = $dir . DIRECTORY_SEPARATOR . $urKey . ".csv";
            $isBig = filesize($file) > static::MAX_FILE_SIZE;
            // 大文件按行读, 否则直接读入数组
            if ($isBig) {
                $urCsv = fopen($file, "r");
            } else {
                $urCsv = file($file, FILE_IGNORE_NEW_LINES);
            }
        }

        for ($i = 0; $i < $k; $i++) {
            $vs = [];
            if ($i + 1 < $k) {
                $chunk = $nk;
            } else {
                $chunk = count($users) - $nk * $i;
            }
            for ($j = 0; $j < $chunk; $j++) {
                $index = $i * $nk + $j;
                if ($dir) {
                    if ($isBig) {
                        $arr = str_getcsv(fgets($urCsv));
                    } else {
                        $arr = str_getcsv($urCsv[$index]);
                    }
                } else {
                    $arr = Cache::get("$urKey.{$users[$index]}");
                }
                // 单位化处理
                $v = new Vector($arr);
                $v = $v->length() < static::EPSILON ? $v : $v->normalize();
                $vs[] = $v;
            }

            // 计算协方差
            $M = MatrixFactory::create($vs);
            $covMatrix = $M->transpose()->multiply($M);
            $covArray = $covMatrix->getMatrix();

            // 保存数据
            if ($dir) {
                $file = $dir . DIRECTORY_SEPARATOR . "$smKey.$i.csv";
                $smCsv = fopen($file, "w");
                foreach ($covArray as $row) {
                    fputcsv($smCsv, $row);
                }
                fclose($smCsv);
            } else {
                Cache::forever("$smKey.$i", $covArray);
            }
            yield [$i + 1, $k];
        }
        if ($dir && $isBig) {
            fclose($urCsv);
        }
    }


    /**
     * 根据用户 id 获取相似度矩阵的存储位置
     * @var int id
     * @return array
     */
    public function userIdToLocation(int $id) : array
    {
        $map = $this->getMap();
        $users = $map["users"];
        // 无此用户的记录
        if (!in_array($id, $users)) {
            return [];
        }
        $k = $map["chunks"];
        $kn = $map["numberPerChunk"];
        $iu = $map["indexOfUsers"];

        // 判断存储位置
        $index = $iu[$id];
        $i = intval(floor($index / $kn));
        $j = $index % $kn;

        return [$i, $j];
    }

    /**
     * 根据用户相似度矩阵的存储位置获取其 id
     * @var array $location
     * @return int
     */
    public function userLocationToId(array $location) : int
    {
        $map = $this->getMap();
        $users = $map["users"];
        $kn = $map["numberPerChunk"];
        $index = $location[0] * $kn + $location[1];
        return $users[$index];
    }

    /**
     * 根据用户 id 获取其相似度向量
     * 返回的向量
     * @var int $id user's id
     * @return array
     */
    public function getSimVecByUser(int $id) : array
    {
        $dir = $this->getDataDir();
        $key = $this->getCacheKey("sim_mat");

        // 判断存储位置
        $location = $this->userIdToLocation($id);
        if (!$location) {
            return [];
        }
        $i = $location[0];
        $j = $location[1];

        // 读取相似度向量
        if ($dir) {
            $file = $dir . DIRECTORY_SEPARATOR . "$key.$i.csv";
            // 总认为分块是合理的, 此文件可以直接读入内存
            $arr = file($file, FILE_IGNORE_NEW_LINES);
            $vec = str_getcsv($arr[$j]);
        } else {
            $arr = Cache::get("$key.$i");
            $vec = $arr[$j];
        }

        return $vec;
    }

    /**
     * 得到长度为 $n 的, 全为 0 的数组
     * array_pad 一次最多填充 2^20 个单元
     * 分多次组合
     * @var int $n length of the array
     * @return array
     */
    public function zerosArray(int $n) : array
    {
        $t1 = intval(floor($n / static::MAX_PAD));
        $nl = $n % static::MAX_PAD;
        $zeros = [];
        for ($i = 0; $i < $t1; $i++) {
            $arr = array_pad([], static::MAX_PAD, 0);
            $zeros = array_merge($zeros, $arr);
        }
        $arr = array_pad([], $nl, 0);
        $zeros = array_merge($zeros, $arr);
        return $zeros;
    }

    // 点击和购买的比例接近 50 : 1
    protected $caseSql = "CASE `action` WHEN 'view' THEN 1 WHEN 'buy' THEN 50 ELSE 0 END AS `score`";
    /**
     * 获取一个用户对于每一个产品的评分，得到评分向量
     * 如果在 phpmyadmin 4.8.3 中对 case 语句使用别名,
     * 查询会误报错, 没有找到原因.
     * @var int $id user id
     * @var array  $ratingArr user rating vector
     * @return array
     */
    public function getRatingByUser(int $id) : array
    {
        $map = $this->getMap();

        $userActions = UserAction::select("product_id", DB::raw($this->caseSql))
            ->where("user_id", "=", $id)
            ->whereIn("product_id", $map["products"]) // 过滤掉只存在于 user_actions 中的 product_id
            ->where(function ($query) {
                $query->where("action", "=", "view")
                    ->orWhere("action", "=", "buy");
            })
            ->orderBy("product_id")
            ->get();

        $ratingArray = $this->zerosArray(count($map["products"]));
        foreach ($userActions as $ua) {
            $index = $map["indexOfProducts"][$ua->product_id];
            $ratingArray[$index] += $ua->score;
        }
        return $ratingArray;
    }

    /**
     * set data store directory
     * @var string $dir
     * @return void
     */
    public function setDataDir(string $dir = null) : void
    {
        if ($dir && is_dir($dir) && is_writable($dir)) {
            // 去掉末尾可能存在的路径分割符
            if ($dir[-1] == DIRECTORY_SEPARATOR) {
                $dir = substr($dir, 0, -1);
            }
            $this->dataDir = $dir;
        } else {
            $this->dataDir = null;
        }
    }

    /**
     * get data store direcotry
     * @var void
     * @return string
     */
    public function getDataDir() : ?string
    {
        return $this->dataDir;
    }

    /**
     * set chunks of users
     * @var int $k
     * @return null
     */
    public function setChunks(int $k) : void
    {
        $this->k = $k;
    }

    /**
     * get chunks of users
     * @var void
     * @return int
     */
    public function getChunks() : int
    {
        return $this->k;
    }

    /**
     * 获取活动用户和全部产品
     * 如果初始化类传入存储目录，将保存映射到文件中
     * 程序执行这一条 sql 语句之后第一次有浏览、购买行为的用户,不参与此次计算
     * 老用户此时产生的行为仍参与计算,所以产品 id 是从所有产品中取
     * @var void
     * @return void
     */
    public function generateMap() : void
    {
        // 取在 users 和 user_actions 中都存在的 user_id
        $users = UserAction::select("user_id")->distinct()
            ->join("users", "user_actions.user_id", "=", "users.id")
            ->orderBy("user_id")
            ->get();

        // 用户 id
        foreach ($users as $u) {
            $ui[] = $u->user_id;
        }
        // 用户索引
        $iu = array_flip($ui);

        $products = Product::select("id")->distinct()->orderBy("id")->get();
        // 产品 id
        foreach ($products as $p) {
            $pi[] = $p->id;
        }
        // 产品索引
        $ip = array_flip($pi);

        // 分块
        $k = $this->getChunks();
        // 每一块的最大数量
        $kn = intval(ceil(count($ui) / $k));
        $map = [
            "users" => $ui,
            "indexOfUsers" => $iu,
            "products" => $pi,
            "indexOfProducts" => $ip,
            "chunks" => $k,
            "numberPerChunk" => $kn,
        ];

        $cacheKey = $this->getCacheKey("map");
        Cache::forever($cacheKey, $map);
        $dir = $this->getDataDir();
        if ($dir) {
            $file = $dir . DIRECTORY_SEPARATOR . $cacheKey . ".json";
            file_put_contents($file, json_encode($map));
        }
        $this->map = $map;
    }

    /**
     * 获取映射
     * @var void
     * @return array
     */
    public function getMap() : array
    {
        return $this->map;
    }

    /**
     * get cache key
     * @var string $key
     * @return mixed
     */
    public function getCacheKey(string $key = null)
    {
        $kvs = $this->cacheKeys;
        if ($key) {
            return $kvs[$key];
        } else {
            return $kvs;
        }
    }

    /**
     * set cache key
     * @var array $kvs
     * @return void
     */
    public function setCacheKey(array $kvs) : void
    {
        $this->cacheKeys = $kvs;
    }

    /**
     * 清除缓存
     * 只清除用户相似度矩阵, 其他数据手动清除
     * 生成当前进度
     * @yield array
     * @return Generator
     */
    public function clearCache() : Generator
    {
        $k = $this->getMap()["chunks"];
        $key = $this->getCacheKey("sim_mat");
        $dir = $this->getDataDir();
        for ($i = 0; $i < $k; $i++) {
            if ($dir) {
                $file = $dir . DIRECTORY_SEPARATOR . "$key.$i.csv";
                unlink($file);
            } else {
                Cache::forget("$key.$i");
            }
            yield [$i + 1, $k];
        }
    }
}
